The invention relates to error detection. More particularly, the invention relates to methods and apparatus for efficiently detecting errors in one-hot words, which have only a single bit set in the absence of errors.
A binary one-hot word is a set of binary bits which have a single bit high and all others low, or a single bit low and all other bits high. For the sake of clarity, this document will refer to the single xe2x80x9chotxe2x80x9d or xe2x80x9csetxe2x80x9d bit in a binary one-hot word as if it were nominally high while and all others are nominally low, even though it is equally possible that the set bit could be nominally low while all others are nominally high. One-hot words are utilized for example as the tag storage in a pre-validated cache. Other uses for one-hot words are apparent to those skilled in the art.
A one-hot word may be corrupted by errors in one or both of two ways generally. In a first form of corruption, the set bit is un-set (i.e., the single one bit is changed to zero). The result of this corruption is a word having all bits zero. As used herein, the term xe2x80x9cmissxe2x80x9d refers to this situation where all bits are zero. Depending upon the application, a miss may or may not be an erroneous condition. For example, a miss in a pre-validated cache is a valid, uncorrupted state, whereas in other applications, a miss is not valid. The other form of corruption of an one-hot word is the setting of one or more bits that should remain low. That is, a one-hot word so corrupted has two or more bits set. As used herein, the term xe2x80x9cmultihitxe2x80x9d is used to refer to a word having two or more bits set, whereas the term xe2x80x9chitxe2x80x9d is used to refer to a word having any one or more bit set.
FIG. 1 shows logic circuitry 100 for detecting certain types of errors in an eight bit one-hot word. The one-hot word has eight constituent bits D0, D1, . . . , D7, and the word is denoted D0:D7. The eight data bits D0, D1, . . . , D7 are input to the logic circuitry 100 from the left, as shown in FIG. 1. Exclusive-OR (XOR) gates 104, 108, 112, 116, 120, 124, and 128 are connected together so as to form an eight input exclusive-OR function. A signal ODD is output from the final exclusive-OR gate 128. The signal ODD is high if the number of bits set in the word D0:D7 is odd; the signal ODD is low if the number of bits set in the word D0:D7 is even.
The logic circuitry 100 also includes NOR gates 140, 144, 148, and 152 connected to NAND gates 156 and 160, which are connected to a NOR gate 164 in such a way that a signal MISS output from the NOR gate 164 is high if and only if every bit of the word DO:D7 is low. An inverter gate 170 is connected to the signal MISS, and a signal HIT is output from the inverter gate 170. The signal HIT is high if one or more of the bits in the word D0:D7 is high. The signals ODD and MISS are input into a NOR gate 174. The output of the NOR gate 174 is a signal EVEN MULTIHIT, which is high when exactly two or exactly four or exactly six or all eight of the data bits D0, D1, . . . , D7 are high. Thus, the logic circuit 100 is capable of detecting certain types of erroneous one-hot words. However, the logic circuit 100 is not capable of detecting all errors in the one-hot word D0:D7. In particular, the logic circuit 100 is not capable of detecting an error in which an odd number of bits is set in the word D0:D7. That is, the cases when exactly is three or exactly five or exactly seven bits in the word D0:D7 are not detected as one-hot errors by the logic circuit 100.
In one respect, the invention is an apparatus for use in detecting errors in one-hot words. The apparatus comprises a plurality of input signal lines, a plurality of switching devices connected to the input switch signal lines, a plurality of intermediate signal lines, and logic circuitry. The switching devices are connected to the input signal lines. The intermediate signal lines are also connected to the switching devices. The connection is in such a way that when a particular input signal line is set, all intermediate signal lines connected by a switching device to that particular input signal line are forced to a predetermined logic state. The intermediate signal lines are input to the logic circuitry, which outputs a signal indicative of whether at least two of the plurality of input signal lines are set.
In another respect, the invention is a method for detecting non-one-hot conditions in a group of M bits. The method encodes the group of M bits into at least 2xc2x7log2M encoded bits, such that each one-hot condition in the group of N bits generates a unique condition in the group of encoded bits. The method determines on the basis of the encoded bits whether the group of M bits are in a non-one-hot condition. It is preferable but not mandatory, that the at least 2xc2x7log2M encoded bits be two groups of at least log2M encoded bits each. For example (and not by way of limitation), the two groups of at least log2M encoded bits can be complement encodings of each other.
In yet another respect, the invention is a method for detecting one-hot errors in a group D of bits. The method first partitions the group D of bits into two non-intersecting subsets S0 and NS0 such that D is the union of S0 and NS0. The method determines whether any of the bits in the subset S0 are hot. The method also determines whether any of the bits in the subset NS0 are hot. The group D is partitioned again into another two completely different non-intersecting subsets S1 and NS1 such that D is the union of S1 and NS1. The method then determines whether any of the bits in S1 are hot and whether any of the bits in NS1 are hot. On the basis of the determinations made so far, the method determines whether the group D contains an error.
In comparison to the logic circuitry 100, certain embodiments of the invention are capable of achieving certain advantages, including the following:
(1) Detection of all non-one-hot words (i.e., all multihits whether even or odd as well as misses if applicable) is possible with certain embodiments of the invention.
(2) Certain embodiments of the invention are capable of processing a one-hot word for the purpose of detecting errors with less delay than the logic circuitry 100. In particular, there are seven gate delays in the logic circuit 100 going from the left side input to the right side output. (Gate delays are counted herein according to the typical convention in which XOR gates introduce two units of delay, while inverters or NAND gates introduce one unit of gate delay). Certain embodiments of the invention, on the other hand, have as little as four gate delays to do the same thing. Furthermore, the number of gate delays is largely independent of the size of (i.e., number of bits in) the one-hot word, whereas that is not the case with the logic circuitry 100.
(3) Certain embodiments of the invention can be physically implemented using less semiconductor area than the logic circuitry 100.